#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void findPrimeNumbers1(int N)
{
  // final int N = 100000; // Find primes <= N
  const int NUMBER_PER_LINE = 10; // Display 10 per line
  int count = 0; // Count the number of prime numbers
  int number = 2; // A number to be tested for primeness

  // Repeatedly find prime numbers
  while (number < N)
  {
    // Assume the number is prime
    bool isPrime = true; // Is the current number prime?

    // Exercise3_21 if number is prime
    for (int divisor = 2; divisor <= (int)(sqrt(number * 1.0)); divisor++)
    {
      if (number % divisor == 0)
      { // If true, number is not prime
        isPrime = false; // Set isPrime to false
        break; // Exit the for loop
      }
    }

    // Check if the next number is prime
    number++;
  }
}

void findPrimeNumbers2(int N)
{
  // A list to hold prime numbers
  vector<int> list;
  // final int N = 10000000; // Find primes <= N
  const int NUMBER_PER_LINE = 10; // Display 10 per line
  int count = 0; // Count the number of prime numbers
  int number = 2; // A number to be tested for primeness

  // Repeatedly find prime numbers
  while (number < N)
  {
    // Assume the number is prime
    bool isPrime = true; // Is the current number prime?

    // Exercise3_21 if number is prime
    for (int k = 0; k < list.size() && list[k] <= (int)(sqrt(number * 1.0)); k++)
    {
      if (number % list[k] == 0)
      { // If true, number is not prime
        isPrime = false; // Set isPrime to false
        break; // Exit the for loop
      }
    }

    // Check if the next number is prime
    number++;
  }
}

int main()
{
  long executionTime[6];
  for (int i = 0; i < 6; i++)
  {
    long startTime = time(0);
    findPrimeNumbers1(8000000 + i * 2000000);
    executionTime[i] = time(0) - startTime;
  }
  cout << "\t\t\t8000000\t10000000\t12000000\t14000000\t16000000\t18000000" << endl;
  cout << "-----------------------------------------------------------------" << endl;
  cout << "Listing 18.4";

  for (int i = 0; i < 6; i++)
  {
    cout << "\t" << executionTime[i];
  }

  cout << "\nListing 18.5";
  for (int i = 0; i < 6; i++)
  {
    long startTime = time(0);
    findPrimeNumbers2(8000000 + i * 2000000);
    executionTime[i] = time(0) - startTime;
  }

  for (int i = 0; i < 6; i++)
  {
    cout << "\t" << executionTime[i];
  }

  return 0;
}
